home *** CD-ROM | disk | FTP | other *** search
/ ASME's Mechanical Engine…ing Toolkit 1997 December / ASME's Mechanical Engineering Toolkit 1997 December.iso / c_lang / ttt2.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-05-26  |  10.0 KB  |  409 lines
  1. /*   This program simulates a constraint satisfaction
  2.      neural network for choosing tic-tac-toe moves as
  3.      described in Volume 2 of the PDP books.  The
  4.      network is presented a description of the board 
  5.      after each move and chooses the best move alternately
  6.      for each side subject to predefined constraints.
  7.  
  8.      It requires an EGA or CGA to display a Hinton diagram 
  9.      of the element activation levels.
  10.  
  11.      Author   : Gary Andriotakis
  12.      Compiler : Microsoft Quick C
  13.      Date     : 5 January 1989
  14. */
  15. #include<stdio.h>
  16. #include <stdio.h>
  17. #include <time.h>
  18. #include <graph.h>
  19. #define N 67
  20. #define GAIN 0.1
  21. #define SCALE 1.0/16.0
  22. static float w[N][N], bias[N], a[N], e[2][N];
  23. main()
  24. {
  25.    int i,j,n,mark = -1,converged;
  26.    time_t t;
  27.    if(!_setvideomode(_ERESCOLOR))
  28.    {   printf("EGA required\n");
  29.        exit(0);
  30.    }
  31.    srand((int)time(&t));
  32.    drawboard();
  33.    n = 1;
  34.    for(i = 0; i < 9; i++)
  35.    {  n = 1 - n;
  36.       if(n)
  37.       {  _settextposition(2,2);
  38.      _outtext("move    x     o   empty   2x    2o    1x    1o");
  39.       }
  40.       else
  41.       {  _settextposition(2,2);
  42.          _outtext("move    o     x   empty   2o    2x    1o    1x");
  43.       }
  44.       putmarkers(&e[n][9],mark,1-n);
  45.       initialize();
  46.       boxes(a,N);
  47.       do
  48.       {  j = randint(N);
  49.          update(j,&e[n][0]);
  50.          boxes(a,j);
  51.          converged = ((j < 9) && (a[j] > 0.9));
  52.       } while(!converged);
  53.       mark = j;
  54.       if(kbhit() && getch() == 27) break;
  55.    }
  56.    _setvideomode(_DEFAULTMODE);
  57.    _displaycursor(_GCURSORON);
  58. }
  59.  
  60. update(j,e)
  61. int j;
  62. float e[N];
  63. {  int i;
  64.    float net;
  65.  
  66.    net = 0.0;
  67.    for(i = 0; i < N; i++)
  68.       net += w[i][j]*a[i];
  69.    net += bias[j];
  70.    net *= GAIN;
  71.    net += e[j];
  72.    if(net > 0.0)
  73.       a[j] += net*(1.0 - a[j]);
  74.    else
  75.       a[j] += net*a[j];
  76. }
  77.  
  78. initialize()
  79. {  int i,j;
  80. /*  initialize to zero */
  81.    for(i = 0; i < N; i++)
  82.    {  a[i] = 0.0;
  83.       bias[i] = 0.0;
  84.       for(j = 0; j < N; j++)
  85.          w[i][j] = 0.0;
  86.    }
  87.  
  88.    for(i = 0; i < 9; i++)
  89.    {  /* inhibit responses from occupied squares */
  90.       w[i+9][i] = -8.0;
  91.       w[i+18][i] = -8.0;
  92.       /*  mutual inhibition to insure only one response */
  93.       for(j = 0; j < 9; j++)
  94.       w[i][j] = -2.;
  95.       w[i][i] = 2.;
  96.    }
  97. /*  empty line detectors */
  98.    for(i = 0; i < 3; i++)
  99.    {  w[i+9][27] = -1.0;
  100.       w[i+18][27] = -1.0;
  101.       w[27][i] = 1.0;
  102.       w[i+12][28] = -1.0;
  103.       w[i+21][28] = -1.0;
  104.       w[28][i+3] = 1.0;
  105.       w[i+15][29] = -1.0;
  106.       w[i+24][29] = -1.0;
  107.       w[29][i+6] = 1.0;
  108.       w[9+4*i][30] = -1.0;
  109.       w[18+4*i][30] = -1.0;
  110.       w[30][4*i] = 1.0;
  111.       w[11+2*i][31] = -1.0;
  112.       w[20+2*i][31] = -1.0;
  113.       w[31][2+2*i] = 1.0;
  114.       w[9+3*i][32] = -1.0;
  115.       w[18+3*i][32] = -1.0;
  116.       w[32][3*i] = 1.0;
  117.       w[10+3*i][33] = -1.0;
  118.       w[19+3*i][33] = -1.0;
  119.       w[33][1+3*i] = 1.0;
  120.       w[11+3*i][34] = -1.0;
  121.       w[20+3*i][34] = -1.0;
  122.       w[34][2+3*i] = 1.0;
  123.    }
  124. /*   friendly doubleton detectors */
  125.    for(i = 0; i < 3; i++)
  126.    {  w[i+9][35] = 1.0;
  127.       w[i+18][35] = -2.0;
  128.       w[35][i] = 5.0;
  129.       w[i+12][36] = 1.0;
  130.       w[i+21][36] = -2.0;
  131.       w[36][i+3] = 5.0;
  132.       w[i+15][37] = 1.0;
  133.       w[i+24][37] = -2.0;
  134.       w[37][i+6] = 5.0;
  135.       w[9+4*i][38] = 1.0;
  136.       w[18+4*i][38] = -2.0;
  137.       w[38][4*i] = 5.0;
  138.       w[11+2*i][39] = 1.0;
  139.       w[20+2*i][39] = -2.0;
  140.       w[39][2+2*i] = 5.0;
  141.       w[9+3*i][40] = 1.0;
  142.       w[18+3*i][40] = -2.0;
  143.       w[40][3*i] = 5.0;
  144.       w[10+3*i][41] = 1.0;
  145.       w[19+3*i][41] = -2.0;
  146.       w[41][1+3*i] = 5.0;
  147.       w[11+3*i][42] = 1.0;
  148.       w[20+3*i][42] = -2.0;
  149.       w[42][2+3*i] = 5.0;
  150.    }
  151. /*   enemy doubleton detectors */
  152.    for(i = 0; i < 3; i++)
  153.    {  w[i+9][43] = -2.0;
  154.       w[i+18][43] = 1.0;
  155.       w[43][i] = 1.0;
  156.       w[i+12][44] = -2.0;
  157.       w[i+21][44] = 1.0;
  158.       w[44][i+3] = 1.0;
  159.       w[i+15][45] = -2.0;
  160.       w[i+24][45] = 1.0;
  161.       w[45][i+6] = 1.0;
  162.       w[9+4*i][46] = -2.0;
  163.       w[18+4*i][46] = 1.0;
  164.       w[46][4*i] = 1.0;
  165.       w[11+2*i][47] = -2.0;
  166.       w[20+2*i][47] = 1.0;
  167.       w[47][2+2*i] = 1.0;
  168.       w[9+3*i][48] = -2.0;
  169.       w[18+3*i][48] = 1.0;
  170.       w[48][3*i] = 1.0;
  171.       w[10+3*i][49] = -2.0;
  172.       w[19+3*i][49] = 1.0;
  173.       w[49][1+3*i] = 1.0;
  174.       w[11+3*i][50] = -2.0;
  175.       w[20+3*i][50] = 1.0;
  176.       w[50][2+3*i] = 1.0;
  177.    }
  178. /*   friendly singleton detectors */
  179.    for(i = 0; i < 3; i++)
  180.    {  w[i+9][51] = 1.0;
  181.       w[i+18][51] = -2.0;
  182.       w[51][i] = 2.0;
  183.       w[i+12][52] = 1.0;
  184.       w[i+21][52] = -2.0;
  185.       w[52][i+3] = 2.0;
  186.       w[i+15][53] = 1.0;
  187.       w[i+24][53] = -2.0;
  188.       w[53][i+6] = 2.0;
  189.       w[9+4*i][54] = 1.0;
  190.       w[18+4*i][54] = -2.0;
  191.       w[54][4*i] = 2.0;
  192.       w[11+2*i][55] = 1.0;
  193.       w[20+2*i][55] = -2.0;
  194.       w[55][2+2*i] = 2.0;
  195.       w[9+3*i][56] = 1.0;
  196.       w[18+3*i][56] = -2.0;
  197.       w[56][3*i] = 2.0;
  198.       w[10+3*i][57] = 1.0;
  199.       w[19+3*i][57] = -2.0;
  200.       w[57][1+3*i] = 2.0;
  201.       w[11+3*i][58] = 1.0;
  202.       w[20+3*i][58] = -2.0;
  203.       w[58][2+3*i] = 2.0;
  204.    }
  205. /*   enemy singleton detectors */
  206.    for(i = 0; i < 3; i++)
  207.    {  w[i+9][59] = -2.0;
  208.       w[i+18][59] = 1.0;
  209.       w[59][i] = 2.0;
  210.       w[i+12][60] = -2.0;
  211.       w[i+21][60] = 1.0;
  212.       w[60][i+3] = 2.0;
  213.       w[i+15][61] = -2.0;
  214.       w[i+24][61] = 1.0;
  215.       w[61][i+6] = 2.0;
  216.       w[9+4*i][62] = -2.0;
  217.       w[18+4*i][62] = 1.0;
  218.       w[62][4*i] = 2.0;
  219.       w[11+2*i][63] = -2.0;
  220.       w[20+2*i][63] = 1.0;
  221.       w[63][2+2*i] = 2.0;
  222.       w[9+3*i][64] = -2.0;
  223.       w[18+3*i][64] = 1.0;
  224.       w[64][3*i] = 2.0;
  225.       w[10+3*i][65] = -2.0;
  226.       w[19+3*i][65] = 1.0;
  227.       w[65][1+3*i] = 2.0;
  228.       w[11+3*i][66] = -2.0;
  229.       w[20+3*i][66] = 1.0;
  230.       w[66][2+3*i] = 2.0;
  231.    }
  232. /* biases */
  233.    for(i = 0; i < 9; i++)
  234.       bias[i] = SCALE;
  235.    for(i = 0; i < 8; i++)
  236.    {  bias[i+27] = 0.5;
  237.       bias[i+35] = -1.5;
  238.       bias[i+43] = -1.5;
  239.       bias[i+51] = -0.5;
  240.       bias[i+59] = -0.5;
  241.     }
  242.     for(i = 0; i < N; i++)
  243.     {  bias[i] *= SCALE;
  244.        for(j = 0; j < N; j++)
  245.       w[i][j] *= SCALE;
  246.     }
  247. }
  248.  
  249. randint(n)
  250. int n;
  251. {
  252.    return(rand() % n);
  253. }
  254.  
  255. #define MAXSIZE 5
  256. boxes(a,n)
  257. float a[];
  258. int n;
  259. {
  260.    int i,j,k,x,y,x0,y0;
  261.    int size,count;
  262.  
  263.    x0 = 5;
  264.    y0 = 40;
  265.    count = -1;
  266.    for(k = 0; k < 3; k++)
  267.    {  x = x0;
  268.       y = y0;
  269.       for(i = 0; i < 3; i++)
  270.       {  for(j = 0; j < 3; j++)
  271.          {  x += 12;
  272.             count++;
  273.             if(n == N || n == count)
  274.             {  size = a[count]*MAXSIZE;
  275.                _setcolor(0);
  276.                _rectangle(_GFILLINTERIOR,
  277.                x-MAXSIZE,y-MAXSIZE,x+MAXSIZE,y+MAXSIZE);
  278.                _setcolor(15);
  279.                _rectangle(_GBORDER,x-size,y-size,x+size,y+size);
  280.             }
  281.          }
  282.          x = x0;
  283.          y += 12;
  284.       }
  285.       x0 += 48;
  286.    }
  287.    y0 = 40;
  288.    for(k = 0; k < 5; k++)
  289.    {  x = x0;
  290.       y = y0;
  291.       for(i = 0; i < 3; i++)
  292.       {  for(j = 0; j < 3; j++)
  293.          {  x += 12;
  294.             if(i != 1 || j != 1)
  295.             {  count++;
  296.                if(n == N || n == count)
  297.                {  size = a[count]*MAXSIZE;
  298.                   _setcolor(0);
  299.                   _rectangle(_GFILLINTERIOR,
  300.                   x-MAXSIZE,y-MAXSIZE,x+MAXSIZE,y+MAXSIZE);
  301.                   _setcolor(15);
  302.                   _rectangle(_GBORDER,x-size,y-size,x+size,y+size);
  303.                }
  304.             }
  305.          }
  306.          x = x0;
  307.          y += 12;
  308.       }
  309.       x0 += 48;
  310.    }
  311. }
  312.  
  313. drawboard()
  314. {  static char board[5][6] = {32,179,32,179,32,0,
  315.                   196,197,196,197,196,0,
  316.                   32,179,32,179,32,0,
  317.                   196,197,196,197,196,0,
  318.                   32,179,32,179,32,0};
  319.    int i;
  320.    _clearscreen(_GCLEARSCREEN);
  321.    for(i = 0; i < 5; i++)
  322.    {  _settextposition(i+8,37);
  323.       _outtext(&board[i][0]);
  324.    }
  325.    _settextposition(19,5);
  326.    _outtext("This is a tic-tac-toe game where a neural network plays");
  327.    _settextposition(20,5);
  328.    _outtext("both sides of the game.  Alternating representations of the");
  329.    _settextposition(21,5);
  330.    _outtext("board are presented to the same network. Hitting");
  331.    _settextposition(22,5);
  332.    _outtext("ESCAPE while the network is running will exit program");
  333.    _settextposition(23,5);
  334.    _outtext("when the current move is complete.");
  335. }
  336.  
  337. putmarkers(b,x,n)
  338. float b[];
  339. int x;              /*  location of programs new move */
  340. /*
  341.  *   puts x's and o's on the board
  342.  *   x is the programs marker,
  343.  *   o is the opponents marker
  344.  */
  345. {  int i,row,col;
  346.    static int board[9] = {0};
  347.    int c, c1;
  348.  
  349.    if(x > -1)
  350.    {  _settextposition(8+2*(x/3),37+2*(x%3));
  351.       if(n == 0)
  352.          _outtext("x");
  353.       else
  354.          _outtext("o");
  355.       board[x] = n+1;
  356.    }
  357.    for(i = 0; i < 9; i++)
  358.    {   if(board[i] == 0)
  359.        {  b[i] = 0.0;
  360.           b[i+9] = 0.0;
  361.        }
  362.        else if(((board[i] == 1) && (n == 0)) ||
  363.                ((board[i] == 2) && (n == 1)))
  364.        {  b[i] = 1.0;
  365.           b[i+9] = 0.0;
  366.        }
  367.        else if(((board[i] == 2) && (n == 0)) ||
  368.                ((board[i] == 1) && (n == 1)))
  369.        {  b[i] = 0.0;
  370.           b[i+9] = 1.0;
  371.        }
  372.    }
  373. }
  374.  
  375. == 0)) ||
  376.                ((board[i] == 1) && (n == 1)))
  377.        {  b[i] = 0.0;
  378.           b[i+9] = 1.0;
  379.        }
  380.    }
  381.       w[49][1+3*i] = 1.0;
  382.       w[11+3*i][50] = -2.0;
  383.       w[20+3*i][50] = 1.0;
  384.       w[50][2+3*i] = 1.0;
  385.    }
  386. /*   friendly singleton detectors */
  387.    for(i = 0; i < 3; i++)
  388.    {  w[i+9][51] = 1.0;
  389.       w[i+18][51] = -2.0;
  390.       w[51][i] = 2.0;
  391.       w[i+12][52] = 1.0;
  392.       w[i+21][52] = -2.0;
  393.       w[52][i+3] = 2.0;
  394.       w[i+15][53] = 1.0;
  395.       w[i+24][53] = -2.0;
  396.       w[53][i+6] = 2.0;
  397.       w[9+4*i][54] = 1.0;
  398.       w[18+4*i][54] = -2.0;
  399.       w[54][4*i] = 2.0;
  400.       w[11+2*i][55] = 1.0;
  401.       w[20+2*i][55] = -2.0;
  402.       w[55][2+2*i] = 2.0;
  403.       w[9+3*i][56] = 1.0;
  404.       w[18+3*i][56] = -2.0;
  405.       w[56][3*i] = 2.0;
  406.       w[10+3*i][57] = 1.0;
  407.       w[19+3*i][57] = -2.0;
  408.       w[57][1+3*i] = 2.0;
  409.       w[11+3*i][58] = 1.0